package com.cty._01_Base._12_StringPathInMatrix;

/**
 * @Auther: cty
 * @Date: 2020/7/2 10:11
 * @Description: 面试题12：矩阵中的路径
 * 题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有
 * 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、
 * 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入
 * 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字
 * 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个
 * 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
 *                a b t g
 *                c f c s
 *                j d e h
 * 回溯法总结：
 *      选择起始位置
 *      进入递归函数
 *          [是否符合结束条件]
 *              符合则结束
 *              不符合则验证当前位置是否符合要求
 *                  不符合要求则结束
 *                  符合要求则记录当前位置并递归下一个位置
 *                      若无符合要求的下一个位置则回溯到上一个位置（即把当前位置的记录删掉）
 * @version: 1.0
 */
public class StringPathInMatrix {

    /**
     * 矩阵中是否存在指定路径
     * @param matrix
     * @param rows
     * @param cols
     * @param strPath
     * @return
     */
    public static boolean hasPath(char[][] matrix, int rows, int cols, String strPath){
        if(matrix==null || rows<1 || cols<1 || strPath==null)
            return false;

        boolean[][] visited = new boolean[rows][cols];
        int indexPath = 0;

        for(int row=0; row<rows; row++)
            for(int col=0; col<cols; col++)
                if(hashPathCore(matrix,rows,cols,strPath,row,col,indexPath,visited))
                    return true;
        return false;
    }  // end hasPath()

    /**
     * 回溯法查找路径
     */
    private static boolean hashPathCore(char[][] matrix, int rows, int cols, String strPath,
                                        int row, int col, int indexPath, boolean[][] visited){
        // 查找结束
        if(strPath.length() <= indexPath)
            return true;

        // 处理当前字符
        boolean isFindNext = false;
        if(row>=0 && row<rows && col>=0 && col<cols &&
                matrix[row][col]==strPath.charAt(indexPath) && !visited[row][col]){
            indexPath++;
            visited[row][col] = true;

            // 查找下一个字符
            isFindNext = hashPathCore(matrix,rows,cols,strPath,row-1,col,indexPath,visited) ||  // 上
                    hashPathCore(matrix,rows,cols,strPath,row+1,col,indexPath,visited) ||  // 下
                    hashPathCore(matrix,rows,cols,strPath,row,col-1,indexPath,visited) ||  // 左
                    hashPathCore(matrix,rows,cols,strPath,row,col+1,indexPath,visited);  // 右

            // 查找不到下一个，回溯到原来状态
            if(!isFindNext){
                indexPath--;
                visited[row][col] = false;
            }
        }  // end if

        return isFindNext;
    }  // end hashPathCore()

}  // end class
